﻿#include <iostream>

using namespace std;

template<class T>
class MaxHeap
{
public:
    MaxHeap(const int &length);
    ~MaxHeap();
    int size();
    void push(const T &element);
    void pop();
    void display();

private:
    int capacity;
    int heapSize;

    T* heap;
};

template <class T>
MaxHeap<T>::MaxHeap(const int  &length)
{
    if(length<1)
    {
        cout<<"the length must more than 1"<<endl;
    }
    capacity=length;
    heapSize=0;
    heap=(T*)new T [length];
    for(int i=0;i<capacity;i++)
    {
        *(heap+i)=(T)0;
    }
}

template <class T>
MaxHeap<T>::~MaxHeap()
{
    delete [] heap;
}

template <class T>
void MaxHeap<T>::push(const T &element)
{
    if(heapSize>capacity-2)    //enlarge the size of the tree
    {
        T* temp=(T*) new T[capacity];
        for(int i=0;i<capacity;i++)
        {
            temp[i]=heap[i];
        }
        delete [] heap;

        heap=(T*) new T [capacity*2];
        for(int i=0;i<capacity*2;i++)
        {
            if(i<heapSize)
            {
                heap[i]=temp[i];
            }
            else heap[i]=0;
        }
        delete []temp;

        capacity*=2;
    }

    int troot=++heapSize;
    while(troot!=1&&heap[troot/2]<element)   //find the insert postion;
    {
        heap[troot]=heap[troot/2];
        troot/=2;
    }

    heap[troot]=element;
}

template<class T>
void MaxHeap<T>::pop()
{
    if(heapSize<1)
        cout<<"the heap is empty"<<endl;

    heap[1]=heap[heapSize];  //从树根部弹出
    heap[heapSize]=0;
    heapSize--;

    int child=1;
    for(int i=1;i*2+1<=heapSize;i++)
    {
        child=child*2;
        if(heap[child]<heap[child+1])  //根节点和最大孩子节点互换
        {
            child++;
        }

        if(heap[i]<heap[child])
        {
            T temp=heap[i];
            heap[i]=heap[child];
            heap[child]=temp;
        }
    }
}

template <class T>
void MaxHeap<T>::display()
{
    for(int i=0;i<capacity;i++)
    {
        if(heap[i]!=0)
        {
            cout<<heap[i]<<"  ";
        }
    }
    cout<<endl;
}

template<class T>
int MaxHeap<T>::size()
{
    return heapSize;
}

int main()
{
    MaxHeap<int> a(10);

    for(int i=1;i<13;i++)
    {
        a.push(i*2);
    }
    cout<<a.size()<<endl;
    a.display();


    a.pop();
    cout<<a.size()<<endl;
    a.display();

    system("pause");
    return 0;
}

// FIXME:
//  1. 写的挺好的，继续努力！
//  2. 写完程序之后，可以检查一下格式（一个TAB用4个空格扩展，函数后面不需要`；`，等等）

